package com.vijos;

//回文数相加
public class P3_1_1304 {

    public static int test(int n, String numStr) {
        int[] num = toInts(numStr);
        int step = 0;
        for (int i = 0; i < 30; i++) {
            step++;
            num = plus(n, num);
            if (isHWS(num)) {
                return step;
            }
        }
        throw new RuntimeException("Impossible!");
    }

    // n进制相加
    private static int[] plus(int n, int[] num) {
        int length = num.length;
        int[] jw = new int[length];
        int[] result = new int[length + 1];
        for (int i = length - 1; i >= 0 ; i--) {
            int t = num[length - 1 - i] + num[i];
            if (i < length - 1 && jw[i + 1] == 1) {
                t += 1;
            }
            if (t >= n) {
                jw[i] = 1;
                t = t - n;
            }
            result[i + 1] = t;
        }
        if (jw[0] == 1) {
            result[0] = 1;
            return result;
        } else {
            int[] newResult = new int[length];
            for (int i = 1; i < result.length; i++) {
                newResult[i - 1] = result[i];
            }
            return newResult;
        }
    }

    // 进制转int数组
    public static int[] toInts(String numStr) {
        char[] chars = numStr.toCharArray();
        int[] num = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (c < 65) {
                num[i] = c - '0';
            } else {
//                value = c - 'A' + 10;
                num[i] = c - 55;
            }
        }
        return num;
    }

    //判断是否为回文数的函数
    private static boolean isHWS(String numberStr){
        char[] chars = numberStr.toCharArray();
        int length = chars.length;
        int mid = length / 2;
        for (int i = 0; i < mid; i++) {
            if (chars[i] != chars[length - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    //判断是否为回文数的函数
    private static boolean isHWS(int[] values) {
        int length = values.length;
        int mid = length / 2;
        for (int i = 0; i < mid; i++) {
            if (values[i] != values[length - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    //判断是否为回文数的函数
    private static boolean isHWS(int number){
        int newNum = 0;
        int tempNum = number;
        while(tempNum != 0){   //颠倒数后保存到temp中
            newNum = newNum * 10 + (tempNum % 10);
            tempNum /= 10;
        }
        if(number == newNum) //是回文数，返回1
            return true;
        else
            return false;
    }

    public static void main(String[] args) {
//        System.out.println(isHWS(123321));
//        System.out.println(isHWS(123321));
//        System.out.println(isHWS(1234321));
//        System.out.println(isHWS(1233321));
//        System.out.println(isHWS(123231));
//        System.out.println(toInts("123123"));
//        System.out.println(toInts("1231AB"));
//        System.out.println(toInts("123"));
        System.out.println("STEP=" + test(9, "87"));
    }
}
